{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 图的实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/directedgraph.jpeg\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用邻接矩阵表示图\n",
    "class GraphMatrix(object):\n",
    "    \n",
    "    def __init__(self, vertices, matrix):\n",
    "        self.vertices = vertices\n",
    "        self.matrix = matrix\n",
    "    \n",
    "    # 深度优先搜索\n",
    "    def dfs_traversal(self):\n",
    "        visited = []\n",
    "        \n",
    "        def dfs(vidx):\n",
    "            if vidx in visited: return\n",
    "            visited.append(vidx)\n",
    "            for aidx, weight in enumerate(self.matrix[vidx]):\n",
    "                if weight < float('inf'): dfs(aidx)\n",
    "        \n",
    "        for idx in range(len(self.vertices)):\n",
    "            if idx not in visited: dfs(idx)\n",
    "        \n",
    "        return [self.vertices[i] for i in visited]\n",
    "    \n",
    "    # 宽度优先搜索\n",
    "    def bfs_traversal(self):\n",
    "        visited = []\n",
    "        \n",
    "        def bfs(vidx):\n",
    "            queue = [vidx]\n",
    "            while queue:\n",
    "                idx = queue.pop(0)\n",
    "                if idx in visited: continue\n",
    "                visited.append(idx)\n",
    "                for aidx, weight in enumerate(self.matrix[vidx]):\n",
    "                    if weight < float('inf'): queue.append(aidx)\n",
    "            \n",
    "        for idx in range(len(self.vertices)):\n",
    "            if idx not in visited: bfs(idx)\n",
    "        \n",
    "        return [self.vertices[i] for i in visited]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']\n",
    "inf = float('inf')\n",
    "matrix = [[inf, 1, 1, 1, inf, inf, inf],  # A\n",
    "          [inf, inf, inf, inf, 1, inf, inf],  # B\n",
    "          [inf, inf, inf, 1, inf, 1, inf],  # C\n",
    "          [inf, 1, inf, inf, 1, inf, 1],  # D\n",
    "          [inf, inf, inf, inf, inf, inf, inf],  # E\n",
    "          [inf, inf, inf, 1, inf, inf, 1],  # F\n",
    "          [inf, inf, inf, inf, 1, inf, inf]]  # G\n",
    "graph1 = GraphMatrix(nodes, matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'E', 'C', 'D', 'G', 'F']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph1.dfs_traversal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C', 'D', 'E', 'F', 'G']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph1.bfs_traversal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用邻接表表示图\n",
    "class GraphList(object):\n",
    "    \n",
    "    def __init__(self, vertices, vert_list):\n",
    "        self.vertices = vertices\n",
    "        self.vert_list = vert_list\n",
    "    \n",
    "    # 深度优先搜索\n",
    "    def dfs_traversal(self):\n",
    "        visited = []\n",
    "        \n",
    "        def dfs(vertice):\n",
    "            if vertice in visited: return\n",
    "            visited.append(vertice)\n",
    "            for adj_vert in self.vert_list[vertice]: dfs(adj_vert)\n",
    "        \n",
    "        for vertice in self.vertices:\n",
    "            if vertice not in visited: dfs(vertice)\n",
    "    \n",
    "        return visited\n",
    "    \n",
    "    # 宽度优先搜索\n",
    "    def bfs_traversal(self):\n",
    "        visited = []\n",
    "        \n",
    "        def bfs(vertice): \n",
    "            queue = [vertice]\n",
    "            while queue:\n",
    "                vertice = queue.pop(0)\n",
    "                if vertice in visited: continue\n",
    "                visited.append(vertice)\n",
    "                for adj_vert in self.vert_list[vertice]: queue.append(adj_vert)\n",
    "        \n",
    "        for vertice in self.vertices:\n",
    "            if vertice not in visited: bfs(vertice)\n",
    "    \n",
    "        return visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']\n",
    "vert_list = {'A': {'B':1, 'C':1, 'D':1},\n",
    "             'B': {'E':1},\n",
    "             'C': {'D':1, 'F':1},\n",
    "             'D': {'B':1, 'E':1, 'G':1},\n",
    "             'E': {},\n",
    "             'F': {'D':1, 'G':1},\n",
    "             'G': {'E':1}}\n",
    "graph2 = GraphList(nodes, vert_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'E', 'C', 'D', 'G', 'F']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph2.dfs_traversal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C', 'D', 'E', 'F', 'G']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph2.bfs_traversal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 997. 找到小镇的法官"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。\n",
    "\n",
    "如果小镇的法官真的存在，那么：\n",
    "\n",
    "小镇的法官不相信任何人。\n",
    "每个人（除了小镇法官外）都信任小镇的法官。\n",
    "只有一个人同时满足属性 1 和属性 2 。\n",
    "\n",
    "给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。\n",
    "\n",
    "如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：N = 2, trust = [[1,2]]\n",
    "输出：2\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：N = 3, trust = [[1,3],[2,3]]\n",
    "输出：3\n",
    "\n",
    "示例 3：\n",
    "\n",
    "输入：N = 3, trust = [[1,3],[2,3],[3,1]]\n",
    "输出：-1\n",
    "\n",
    "示例 4：\n",
    "\n",
    "输入：N = 3, trust = [[1,2],[2,3]]\n",
    "输出：-1\n",
    "\n",
    "示例 5：\n",
    "\n",
    "输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]\n",
    "输出：3\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= N <= 1000\n",
    "trust.length <= 10000\n",
    "trust[i] 是完全不同的\n",
    "trust[i][0] != trust[i][1]\n",
    "1 <= trust[i][0], trust[i][1] <= N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_judge(N, trust):\n",
    "    in_count = [0] * N # 入度统计\n",
    "    for a, b in trust:\n",
    "        in_count[a - 1] = -1 # 出度不为0，则没有统计入度的资格\n",
    "        if in_count[b - 1] >= 0: in_count[b - 1] += 1\n",
    "    for i, time in enumerate(in_count):\n",
    "        if time == N - 1: return i + 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_judge(2, [[1,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_judge(3, [[1,3], [2,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_judge(3, [[1,3], [2,3], [3,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_judge(3, [[1,2], [2,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_judge(4, [[1,3], [1,4], [2,3], [2,4], [4,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_judge(1, [])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 785. 判断二分图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定一个无向图graph，当这个图为二分图时返回true。\n",
    "\n",
    "# 如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。\n",
    "\n",
    "# graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。\n",
    "# 这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。\n",
    "\n",
    "\n",
    "# 示例 1:\n",
    "# 输入: [[1,3], [0,2], [1,3], [0,2]]\n",
    "# 输出: true\n",
    "\n",
    "# 解释: \n",
    "# 无向图如下:\n",
    "# 0----1\n",
    "# |    |\n",
    "# |    |\n",
    "# 3----2\n",
    "# 我们可以将节点分成两组: {0, 2} 和 {1, 3}。\n",
    "\n",
    "# 示例 2:\n",
    "# 输入: [[1,2,3], [0,2], [0,1,3], [0,2]]\n",
    "# 输出: false\n",
    "\n",
    "# 解释: \n",
    "# 无向图如下:\n",
    "# 0----1\n",
    "# | \\  |\n",
    "# |  \\ |\n",
    "# 3----2\n",
    "# 我们不能将节点分割成两个独立的子集。\n",
    "\n",
    "# 注意:\n",
    "\n",
    "# graph 的长度范围为 [1, 100]。\n",
    "# graph[i] 中的元素的范围为 [0, graph.length - 1]。\n",
    "# graph[i] 不会包含 i 或者有重复的值。\n",
    "# 图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 深度优先遍历图，并交替将遍历到的节点标记为0和1，如果出现矛盾，则不是二分图，立即返回False\n",
    "def is_bipartite(graph):\n",
    "    state = [-1] * len(graph)\n",
    "    \n",
    "    def dfs(idx, val):\n",
    "        if state[idx] >= 0: return state[idx] == val\n",
    "        state[idx] = val\n",
    "        for adj_idx in graph[idx]:\n",
    "            if not dfs(adj_idx, 1 - val): return False\n",
    "        return True\n",
    "            \n",
    "    return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_bipartite([[1,3], [0,2], [1,3], [0,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_bipartite([[1,2,3], [0,2], [0,1,3], [0,2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_bipartite([[]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_bipartite([[1], [0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_bipartite([[1,2], [0,2], [0,1]])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3(py37)",
   "language": "python",
   "name": "py37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
